/**************************
* @Summary
* @Author 20009200303 赵传博
* @Date 6/2/2022
*****************************/


#ifndef HW15_2_QSORTFACTORY_H
#define HW15_2_QSORTFACTORY_H

template<typename T>
class QSortFactory {
public:

    static void sort(T* datas, int length, bool(*order)(T a, T b));

    //快速排序核心，第三个参数是函数指针，要么是ascend，要么是descend
    static void qSort(T* datas, int low, int high, bool(*order)(T a, T b));

    static bool ascend(T a, T b);
    static bool descend(T a, T b);
};

template<typename T>
bool QSortFactory<T>::ascend(T a, T b) {
    return a >= b;
}

template<typename T>
bool QSortFactory<T>::descend(T a, T b) {
    return a <= b;
}

template<typename T>
void QSortFactory<T>::sort(T *datas, int length, bool (*order)(T, T)) {
    int low = 0;                //第一个元素下标
    int high = length - 1;      //最后一个元素下标
    qSort(datas, low, high, order);
}

template<typename T>
void QSortFactory<T>::qSort(T *datas, int low, int high, bool (*order)(T, T)) {
    if(low < high){     //第一次：datas长度合理；之后：
        int mid = (high + low) / 2;
        if(datas[mid] > datas[high]){
            T temp = datas[mid];
            datas[mid] = datas[high];
            datas[high] = temp;
        }
        if(datas[low] > datas[high]){
            T temp = datas[low];
            datas[low] = datas[high];
            datas[high] = temp;
        }
        if(datas[mid] > datas[low]){
            T temp = datas[mid];
            datas[mid] = datas[low];
            datas[low] = temp;
        }

        T pivot = datas[low];

        int i = low, j = high;
        while(i != j){
            while(order(datas[j], pivot) && j > i) j--;
            while(order(pivot, datas[i]) && j > i) i++;
            if(i < j){
                T temp = datas[i];
                datas[i] = datas[j];
                datas[j] = temp;
            }
        }

        T temp = datas[low];
        datas[low] = datas[i];
        datas[i] = temp;

        qSort(datas, low, i - 1, order);
        qSort(datas, i + 1, high, order);
    }
}
// 1 3 5 4 6




#endif //HW15_2_QSORTFACTORY_H
